package main

import (
	"errors"
	"fmt"
)

func main() {
	la := LinkedArray{}
	la.Insert(struct{ Name string }{Name: "路飞"}, 0)
	la.Insert(struct{ Name string }{Name: "乔巴"}, 1)
	la.Insert(struct{ Name string }{Name: "山治"}, 0)

	fmt.Println(la.Get(0))
	fmt.Println(la.Get(1))
	removedNode, _ := la.Remove(1)
	fmt.Println(removedNode)
	fmt.Println("输出链表元素")
	la.Output()
}

type Node struct {
	Data interface{}
	Next *Node
}

func NewNode(data interface{}) *Node {
	return &Node{Data: data}
}

//LinkedArray 非协程安全的单向链表
type LinkedArray struct {
	head *Node
	last *Node
	size int
}

func (la *LinkedArray) GetSize() int {
	return la.size
}

func (la *LinkedArray) Get(index int) (*Node, error) {
	if index < 0 || index >= la.size {
		return nil, errors.New("超出链表范围")
	}
	tmp := la.head
	for i := 0; i < index; i++ {
		tmp = tmp.Next
	}

	return tmp, nil
}

func (la *LinkedArray) Insert(data interface{}, index int) error {
	if index < 0 || index > la.size {
		return errors.New("超出链表范围")
	}
	insertedNode := NewNode(data)
	//第一个元素
	if la.size == 0 {
		//第一个元素既是头部也是尾部
		la.head = insertedNode
		la.last = insertedNode
	} else if index == 0 { //插入头部
		//插入头部时，当前插入元素的下一个元素是原头部
		//然后原头部替换为插入元素
		insertedNode.Next = la.head.Next
		la.head = insertedNode
	} else if index == la.size {
		//插入索引等于链表元素个数时，则表示插入尾部
		//原尾部的下一个元素是当期插入元素
		//替换原尾部为当前元素
		la.last.Next = insertedNode
		la.last = insertedNode
	} else { //插入到链表中间
		//所谓的插入中间 就是把插入位置的原元素作为插入元素的下一个元素
		//插入位置的前一个元素的下一个元素是当前新插入元素
		//因此需要获得插入位置的前一个元素
		prevNode, _ := la.Get(index - 1)
		insertedNode.Next = prevNode.Next
		prevNode.Next = insertedNode
	}

	la.size++
	return nil
}

func (la *LinkedArray) Remove(index int) (interface{}, error) {
	if index < 0 || index >= la.size {
		return nil, errors.New("index超出链表范围")
	}
	var removedNode *Node
	if index == 0 { //删除头元素
		removedNode = la.head
		//删除头元素就是把头元素置为原本头的Next
		la.head = la.head.Next
	} else if index == la.size-1 { //删除尾元素
		//获取倒数第二个元素
		prevNode, _ := la.Get(index - 1)
		removedNode = prevNode.Next
		prevNode.Next = nil
		la.last = prevNode
	} else { //删除中间元素
		//获取待删除中间元素的前一个元素
		prevNode, _ := la.Get(index - 1)
		removedNode = prevNode.Next
		prevNode.Next = prevNode.Next.Next
	}

	la.size--
	return removedNode, nil
}

func (la *LinkedArray) Output() {
	tmp := la.head
	for tmp != nil {
		fmt.Println(tmp.Data)
		tmp = tmp.Next
	}
}
